package com.love.dynamic;




public class Decode {


    public static void main(String[] args) {

        char[] nchar = {'1','1','2','4','6'};
        int i = numDecode(nchar, 0);
        System.out.println(i);
    }

    public static int numDecode(char[] nums,int i){
        if(i == nums.length){
            return 1;
        }
        if(nums[i] == '0'){
            return 0;
        }
        int ans;
        ans = numDecode(nums,i+1);
        if(i + 1 < nums.length && (nums[i] - '0') * 10 + (nums[i+1] - '0') <= 26 ){
            ans += numDecode(nums,i+2);
        }
        return ans;
    }


    public static int numDecode(char[] nums,int i,int[] dp){
        if(i == nums.length){
            return 1;
        }
        if(dp[i] != -1){
            return dp[i];
        }
        if(nums[i] == '0'){
            return 0;
        }
        int ans;
        ans = numDecode(nums,i+1);
        if(i + 1 < nums.length && (nums[i] - '0') * 10 + (nums[i+1] - '0') <= 26 ){
            ans += numDecode(nums,i+2);
        }
        dp[i] = ans;
        return ans;
    }


    public static int numDecode(char[] nums){

        int n = nums.length;
        // （n + 1）个数，dp[0...n]
        // 含义：在 i 位置的数之后能多少种转码方式
        int[] dp = new int[n + 1];

        // 从后往前推，前面依赖后面的结果
        dp[n] = 1;
        for (int i = n -1 ; i >= 0 ; i--) {
            if(nums[i] == '0'){
                dp[i] = 0;
            }else {
                dp[i] = dp[i+1];
                if(i + 1 < nums.length && (nums[i] - '0') * 10 + (nums[i+1] - '0') <= 26 ){
                    dp[i] += dp[i+2];

                }
            }
        }


        return dp[0];
    }



}
